package com.lsh.day09_heap;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.HashMap;
import java.util.List;

/**
 * @author ：LiuShihao
 * @date ：Created in 2022/3/21 4:41 下午
 * @desc ：加强堆
 * 在系统实现的PriorityQueue中，没有实现索引表：
 * 如果在已经排好序的小根堆中，调整了某个元素的值，则需要重新排序，
 * 但是系统实现的小根堆PriorityQueue不知道此时元素的位置，所以需要额外遍历一遍
 *
 *
 */
public class HeapGreater<T> {

        private ArrayList<T> heap;
        private HashMap<T,Integer> indexMap;//反向索引表
        private int heapSize;
        private Comparator<? super T> comp;

        public HeapGreater(Comparator c){
            heap = new ArrayList<>();
            indexMap = new HashMap<>();
            heapSize = 0;
            comp = c;
        }

        public boolean isEmpty(){
            return heapSize == 0;
        }

        public int size(){
            return heapSize;
        }

        public boolean contains(T t){
            return indexMap.containsKey(t);
        }

        public T peek(){
            return heap.get(0);
        }

        public void  push(T obj){
            heap.add(obj);
            indexMap.put(obj, heapSize);
            heapInsert(heapSize++);
        }
        public T pop() {
            T ans = heap.get(0);
            swap(0, heapSize - 1);
            indexMap.remove(ans);
            heap.remove(--heapSize);
            heapify(0);
            return ans;
        }

        public void remove(T obj) {
            T replace = heap.get(heapSize - 1);
            int index = indexMap.get(obj);
            indexMap.remove(obj);
            heap.remove(--heapSize);
            if (obj != replace) {
                heap.set(index, replace);
                indexMap.put(replace, index);
                resign(replace);
            }
        }

        public void resign(T obj) {
            heapInsert(indexMap.get(obj));
            heapify(indexMap.get(obj));
        }

        // 请返回堆上的所有元素
        public List<T> getAllElements() {
            List<T> ans = new ArrayList<>();
            for (T c : heap) {
                ans.add(c);
            }
            return ans;
        }

        private void heapInsert(int index) {
            while (comp.compare(heap.get(index), heap.get((index - 1) / 2)) < 0) {
                swap(index, (index - 1) / 2);
                index = (index - 1) / 2;
            }
        }

        private void heapify(int index) {
            int left = index * 2 + 1;
            while (left < heapSize) {
                int best = left + 1 < heapSize && comp.compare(heap.get(left + 1), heap.get(left)) < 0 ? (left + 1) : left;
                best = comp.compare(heap.get(best), heap.get(index)) < 0 ? best : index;
                if (best == index) {
                    break;
                }
                swap(best, index);
                index = best;
                left = index * 2 + 1;
            }
        }

        private void swap(int i, int j) {
            T o1 = heap.get(i);
            T o2 = heap.get(j);
            heap.set(i, o2);
            heap.set(j, o1);
            indexMap.put(o2, i);
            indexMap.put(o1, j);
        }



}
